package lottery;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 
 * @author Qu huanwen
 *
 */
public class Lottery {

	public static void main(String[] args) {
		Lottery lot = new Lottery();
		printArray(lot.sortByOdds(new String[] { "PICK ANY TWO: 10 2 F F",

		"PICK TWO IN ORDER: 10 2 T F", "PICK TWO DIFFERENT: 10 2 F T",
				"PICK TWO LIMITED: 10 2 T T" }));

		printArray(lot.sortByOdds(new String[] { "INDIGO: 93 8 T F",

		"ORANGE: 29 8 F T", "VIOLET: 76 6 F F", "BLUE: 100 8 T T",
				"RED: 99 8 T T", "GREEN: 78 6 F T", "YELLOW: 75 6 F F" }));
		printArray(lot.sortByOdds(new String[] {}));

	}

	private static void printArray(String[] a) {
		for (String s : a) {
			System.out.println(s);
		}
	}

	private class Ticket implements Comparable<Ticket> {
		String name;
		int choices, blanks;
		boolean sorted, unique;
		BigInteger possibleTickets;

		public Ticket(String t) {
			String[] parts = t.trim().split(":");
			name = parts[0];
			String[] tokens = parts[1].trim().split(" ");
			choices = Integer.parseInt(tokens[0]);
			blanks = Integer.parseInt(tokens[1]);
			sorted = "T".equals(tokens[2]) ? true : false;
			unique = "T".equals(tokens[3]) ? true : false;

			calcPossibleTickets();
		}

		private void calcPossibleTickets() {
			if (!sorted && !unique) {
				possibleTickets = power(choices, blanks);
			} else if (sorted && !unique) {
				possibleTickets = combination(choices + blanks - 1, blanks);
			} else if (!sorted && unique) {
				possibleTickets = combination(choices, blanks).multiply(
						permutation(blanks, blanks));
			} else if (sorted && unique) {
				possibleTickets = combination(choices, blanks);
			}
		}

		@Override
		public int compareTo(Ticket t) {
			int c = possibleTickets.compareTo(t.possibleTickets);
			if (c == 0)
				return name.compareTo(t.name);
			else
				return c;
		}
	}

	public String[] sortByOdds(String[] rules) {
		List<Ticket> tickets = new ArrayList<Lottery.Ticket>(rules.length);
		for (String rule : rules) {
			tickets.add(new Ticket(rule));
		}
		Collections.sort(tickets);
		String[] result = new String[tickets.size()];
		for (int i = 0; i < result.length; i++) {
			result[i] = tickets.get(i).name;
		}
		return result;
	}

	private BigInteger power(int n, int m) {
		return BigInteger.valueOf(n).pow(m);
	}

	private BigInteger permutation(int n, int m) {
		return factorial(1, n).divide(factorial(1, n - m));
	}

	private BigInteger combination(int n, int m) {
		return factorial(n, n - m + 1).divide(factorial(1, m));
	}

	private BigInteger factorial(int from, int to) {
		if (from > to) {
			int t = to;
			to = from;
			from = t;
		}
		if (from == 0)
			from = 1;
		BigInteger n = BigInteger.ONE;
		for (int i = from; i <= to; i++) {
			n = n.multiply(BigInteger.valueOf(i));
		}
		return n;
	}
}